class MedianFinder {
    PriorityQueue<Integer> l;
    PriorityQueue<Integer> r;
    public MedianFinder() {
        l=new PriorityQueue<Integer>((a,b)->b-a);
        r=new PriorityQueue<Integer>();
    }
    
    public void addNum(int num) {
        if(l.size()==r.size()){
            if(l.isEmpty()||num<=l.peek()){
                l.offer(num);
            }else{
                r.offer(num);
                l.offer(r.poll());
            }
        }else{
            if(num<=l.peek()){
                l.offer(num);
                r.offer(l.poll());
            }else{
                r.offer(num);
            }
        }
    }
    
    public double findMedian() {
        if(l.size()==r.size()){
            return (l.peek()+r.peek())/2.0;
        }else{
            return l.peek();
        }
    }
}